package com.yiwenup.leetcode.hot;

import com.yiwenup.leetcode.TreeNode;

/**
 * @PROJECT struct-algorithm
 * @PACKAGE com.yiwenup.leetcode.hot
 * @Author yiwenup
 * @Date 2022-03-09 21:44:15
 * <p>
 * @DESCRIPTION https://leetcode-cn.com/problems/convert-bst-to-greater-tree/
 */
public class No0538 {

    private int pre = 0;

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：41.6 MB, 在所有 Java 提交中击败了14.74%的用户
     */
    public TreeNode convertBST(TreeNode root) {
        inOrder(root);
        return root;
    }

    private void inOrder(TreeNode node) {
        if (node == null) return;

        inOrder(node.right);
        node.val += pre;
        pre = node.val;
        inOrder(node.left);
    }
}
